53. Maximum Subarray

接下來我們挑 53. Maximum Subarray 的題目，這個題目直接用窮舉或暴力法可能會有時間上的疑慮。因此，需要思考如何用比較有效率的方法來解題。而這一題在解題的過程中，如何搭配算法的特性將所需的資訊暫存下來而不用每次都浪費迴圈的時間進行運算。

先看一下題目描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.

再搭配範例理解題目

• Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

• Example 2:

Input: nums = [5,4,-1,7,8]
Output: 23

這個題目從範例中很好理解，要從一個陣列中找出總和最大的「subarray」，題目中也有特別補充「subarray 是指原陣列中連續部分所組成的陣列」。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：暴力法

第一種方法當然就是先用暴力法計算 subarray 的數值，將最大的那一組留下來。這裡可以使用兩層的迴圈，將每一個點作為起點的所有可能列出來計算。

用 Python 實作一次

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        m = float("-inf");
        for i in range(len(nums)):
            s = 0;
            for j in range(i+1, len(nums)):
                s += nums[j]
                if s > m:
                    m = s
        return m;

也可以用 JavaScript 復刻一次

var maxSubArray = function(nums) {
  const len = nums.length;
  let max = -Number.MAX_VALUE;
  let sum = 0;
  for (let i = 0; i < len; i++) {
    sum = 0;
    for (let j = i; j < len; j++) {
      sum += nums[j];
      if (sum > max) {
        max = sum;
      }
    }
  }
  return max;
}

不過這樣解法在跑範例的時候可以通過，但是實際上跑測資時會出現 Time Limit Exceeded 的錯誤。

方法 ②：累加法（Greedy）

第一種方法的的概念是「使用兩層的迴圈，將每一個點作為起點的所有可能列出來」，第二層迴圈會將每一個位置後的每一種可能進行累加，例如以下這個例子：

[-2,1,-3,4,-1,2,1,-5,4]

第一個迴圈會找出：

* -2
* 1
* -3
...

第二個迴圈會從每一個位置在往後延伸：

* -2
  * -2 + 1
  * -2 + 1 + -3
  * -2 + 1 + -3 + 4 
  * -2 + ...

* 1
  * 1 + -3
  * 1 + -3 + 4 
  * 1 + ...

講到這裡，你有發現什麼了嗎？對，沒錯，每次都從頭開始找！但實際上「-2 + 1 + -3 + 4 」應該可以沿用「-2 + 1 + -3」累加的結果往後增加即可，第二種方法就是每回合只要往後累加新的元素進行比較就好。

用 Python 實作一次

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = nums[0]
        for num in nums:
            curSum = max(curSum + num, num)
            maxSum = max(maxSum, curSum)
        return maxSum

也可以用 JavaScript 復刻一次

var maxSubArray = function(nums) {
  var maxSum = nums[0],curSum = nums[0];
  for(let num of nums){
    curSum = Math.max(curSum + num, num);
    maxSum = Math.max(maxSum, curSum);
  }
  return maxSum;
};

方法 ③：累加法（DP）

第二種方法我們會用一個變數「curSum」來存放累加的結果，第三種方法我們進一步將累加的結果直接暫存在原陣列中。換句話說，利用原始的陣列將 subarray 加總的結果記錄下來。

用 Python 實作一次

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] = nums[i] + nums[i-1]
            res = max(res, nums[i])
        return res

也可以用 JavaScript 復刻一次

var maxSubArray = function(nums) {
  let res = nums[0];
  for (let i = 1; i < nums.length; ++i) {
    if (nums[i - 1] > 0)
      nums[i] += nums[i - 1];
    res = Math.max(res, nums[i]);
  }
  return res;
};

反思沉澱

這題想跟介紹是的除了窮舉法/暴力法之外，我們常見有幾種不同的方法可以來進行演算法的優化。這題用的分別是「Greedy（貪婪法）」與「Dynamic Programming（動態規劃法）」，這裡先用直覺的方法走過一次，後面再花比較多時間進行討論。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 121. Best Time to Buy and Sell Stock
• 152. Maximum Product Subarray
• 697. Degree of an Array
• 1749. Maximum Absolute Sum of Any Subarray

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。